Pattern search ranking and selection algorithms for mixed variable simulation-based optimization

The class of generalized pattern search (GPS) algorithms for mixed variable optimization is extended to problems with stochastic objective functions. Because random noise in the objective function makes it more difficult to compare trial points and ascertain which points are truly better than others, replications are needed to generate sufficient statistical power to draw conclusions. Rather than comparing pairs of points, the approach taken here augments pattern search with a ranking and selection (R&S) procedure, which allows for comparing many function values simultaneously. Asymptotic convergence for the algorithm is established, numerical issues are discussed, and performance of the algorithm is studied on a set of test problems.     

Pattern transfer fidelity in capillary force lithography with poly(ferrocenylsilane) plasma etch resists

The influence of processing conditions and polymer architecture on pattern transfer in capillary force lithography (CFL) using poly(ferrocenylsilane) etch resists is investigated. Zero-shear-rate viscosities measured at different temperatures and for polymers with different molar masses are related to the quality of CFL patterns, assessed based on atomic force microscopy experiments. An optimal range of viscosities corresponding to appropriate molar masses and processing temperatures is established. In this range, polymers possess enough mobility allowing for reasonably quick surface pattern formation. Yet, the polymers are not too mobile and preserve their shape when quenched to below T_g prior to serving as etch resist masks.     

An Interactive Method for 0-1 Multiobjective Problems Using Simulated Annealing and Tabu Search

This paper presents an interactive method for solving general 0-1 multiobjective linear programs using Simulated Annealing and Tabu Search. The interactive protocol with the decision maker is based on the specification of reservation levels for the objective function values. These reservation levels narrow the scope of the search in each interaction in order to identify regions of major interest to the decision maker. Metaheuristic approaches are used to generate potentially nondominated solutions in the computational phases. Generic versions of Simulated Annealing and Tabu Search for 0-1 single objective linear problems were developed which include a general routine for repairing unfeasible solutions. This routine improves significantly the results of single objective problems and, consequently, the quality of the potentially nondominated solutions generated for the multiobjective problems. Computational results and examples are presented.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

Pure adaptive search in monte carlo optimization

Pure adaptive search constructs a sequence of points uniformly distributed within a corresponding sequence of nested regions of the feasible space. At any stage, the next point in the sequence is chosen uniformly distributed over the region of feasible space containing all points that are equal or superior in value to the previous points in the sequence. We show that for convex programs the number of iterations required to achieve a given accuracy of solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.     

Classification of chromatographic data using multidimensional polynomials

Summary A pattern recognition methodology has been developed for analysis of chromatographic data. The method uses a new class of multidimensional orthogonal polynomials developed by Cohen in conjunction with a supervised learning technique. The method is applicable to any chromatographic data for which classification into two or more categories is desired. The algorithm analyzes both elution times and peak areas. An application is shown for the analysis of organic acids in ascitic fluid obtained from patients with liver disorders. Classification of these patients for presence or absence of bacterial infection shows over ninety percent correct classification.     

A multi-start global minimization algorithm with dynamic search trajectories

A new multi-start algorithm for global unconstrained minimization is presented in which the search trajectories are derived from the equation of motion of a particle in a conservative force field, where the function to be minimized represents the potential energy. The trajectories are modified to increase the probability of convergence to a comparatively low local minimum, thus increasing the region of convergence of the global minimum. A Bayesian argument is adopted by which, under mild assumptions, the confidence level that the global minimum has been attained may be computed. When applied to standard and other test functions, the algorithm never failed to yield the global minimum.The first author wishes to thank Prof. M. Levitt of the Department of Chemical Physics of the Weizmann Institute of Science for suggesting this line of research and also Drs. T. B. Scheffler and E. A. Evangelidis for fruitful discussions regarding Conjecture 2.1. He also acknowledges the exchange agreement award received from the National Council for Research and Development in Israel and the Council for Scientific and Industrial Research in South Africa, which made possible the visit to the Weizmann Institute where this work was initiated.     

Adaptive nonmonotone line search method for unconstrained optimization

In this paper, an adaptive nonmonotone line search method for unconstrained minimization problems is proposed. At every iteration, the new algorithm selects only one of the two directions: a Newton-type direction and a negative curvature direction, to perform the line search. The nonmonotone technique is included in the backtracking line search when the Newton-type direction is the search direction. Furthermore, if the negative curvature direction is the search direction, we increase the steplength under certain conditions. The global convergence to a stationary point with second-order optimality conditions is established. Some numerical results which show the efficiency of the new algorithm are reported.